﻿# include <iostream>
# include <map>
# include <vector>
# include <string>
# include <queue>
# include <fstream>
# define SIZE 10
using namespace std;

class AhoCorasick{
private:
    class BorNode;
    typedef map<char, BorNode*> LinksMap;

    class BorNode {
    friend class AhoCorasick;
    private:
        LinksMap links;  // Всевозможные переходы из текущей вершины по букве
        BorNode *fail;  // Предыдущее состояние для функции отката. Только для root равно NULL.
        BorNode *term; // Ближайшее терминальное состояние. Если отстутствует - NULL
        int out;

    public:
        BorNode(BorNode* fail_node = NULL): fail(fail_node), term(NULL), out(-1) {}

        BorNode* getLink(char c) const{
            LinksMap::const_iterator iter = links.find(c);
            if (iter != links.end()){
                return iter->second;
            }
            else {
                return NULL;
            }
        }

        bool isTerminal() const{
            return (out >= 0);
        }
    };

public:
    void addString(string str){
        BorNode* current_node = &this->root;
        char cp;
        for(int i = 0;i != str.length(); i++){
            cp = str[i];
            BorNode* child_node = current_node->getLink(cp);
            if (child_node == NULL){
                child_node = new BorNode(&root);//изначально все откатываются в root.правильные cуффикные ссылки будут постоены при вызове init
                current_node->links[cp] = child_node;
            }
            current_node = child_node;
        }
        current_node->out = words.size();//если вершина терминальная,в out храним номер строки для поиска. иначе -1
        words.push_back(str);
    }

    void init(){
        queue<BorNode*> q;
        q.push(&root);
        while (!q.empty()){
            BorNode* current_node = q.front();
            q.pop();
            for (LinksMap::const_iterator iter = current_node->links.begin();
                                   iter != current_node->links.end(); iter++){
                char symbol = iter->first;
                BorNode* child = iter->second;
                q.push(child);
                // определение ссылки для отката от дочернего узла
                BorNode* temp_node = current_node->fail;
                while (temp_node != NULL){
                    BorNode* fail_candidate = temp_node->getLink(symbol);
                    if (fail_candidate != NULL){
                        child->fail = fail_candidate;
                        break;
                    }
                    temp_node = temp_node->fail;
                }

                // определение ближайшего предыдущего терминального для дочернего узла
                    if (child->fail->isTerminal()){
                        child->term = child->fail;
                    }
                    else{
                        child->term = child->fail->term;
                    }
            }
        }
    }

    void step(char c){
        while (current_state != NULL){
            BorNode* candidate = current_state->getLink(c);
            if (candidate != NULL){
                current_state = candidate;
                return;
            }
            current_state = current_state->fail;
        }
        current_state = &root;
    }

    void printTermsForCurrentState(ofstream& out,int& haveFound,const int& size,const long& currentPosition,long& lengthBetweenStrings,long& number) const{
        //самое первое найденное - самое длинное
        if (current_state->isTerminal()){
            long pos = out.tellp();
            long step = words[current_state->out].length();
            if(lengthBetweenStrings < step){
                step = lengthBetweenStrings;
                out.seekp (pos - step);
                for (int i = 0; i < step; i++){
                    out<<" ";
                }
                out.seekp (pos - step);
            }else{
                out.seekp (pos - step);
                out<<"*";
                number++;
                for (int i = 0; i < step - 1; i++){
                    out<<" ";
                }
                out.seekp (pos - step + 1);

            }//за счет пробелов после выполнения алгоритма не будет оставаться огрызков запрещенных не перекрытых слов
            lengthBetweenStrings = 0;
            if (haveFound < size){
                haveFound++;
                cout<<words[current_state->out]<<" at position "<<currentPosition - words[current_state->out].length()<<"\n";
            }
        }
        BorNode* temp_node = current_state->term;
        while (temp_node != NULL && haveFound < size){
            haveFound++;
            cout<<words[temp_node->out]<<" .at position "<<currentPosition - words[temp_node->out].length()<<"\n";
            temp_node = temp_node->term;
        }
    }

    void search(ifstream& in, ofstream& out, int size){
        long numberOfStrings = 0;
        current_state = &root;
        char symbol;
        int haveFound = 0;
        long currentPosition = 1;
        long lengthBetweenStrings = 0;
        while(!in.eof()){
            symbol = in.get();
            lengthBetweenStrings++;
            if (symbol != EOF){
                out<<symbol;
                //введем нумерацию не учитывающую символа перевода строки
                if (symbol != '\n'){
                    currentPosition++;
                }
                step(symbol);
                printTermsForCurrentState(out, haveFound, size,currentPosition,lengthBetweenStrings,numberOfStrings);
            }
        }
        cout<<"...\nhave found "<<numberOfStrings<<" forbidden strings";
    }


private:
    BorNode root;
    vector<string> words;
    BorNode* current_state;
};


int main(){
    AhoCorasick ahoCorasick;

    ifstream stop ("stopwords.txt");
    string str;
    while (!stop.eof()){
        stop>>str;
        if (str.length() != 0){
            ahoCorasick.addString(str);
        }
    }
    stop.close();
    ahoCorasick.init();
    ifstream in ("input.txt");
    ofstream out ("output.txt");

    ahoCorasick.search(in,out,SIZE);
    in.close();
    out.close();
    return 0;
}

